import heapq
from typing import List


# TrieNode 是 Trie 树的节点，每个节点存储了指向其子节点的引用和该节点所表示字符串的唯一标识符（sid）
class TrieNode:
    def __init__(self):
        # 存储 26 个字母的子节
        self.children = [None] * 26
        # 字符串的唯一标识符
        self.sid = -1


# Trie 类是用于存储字符串集合的 Trie 树的实现。它提供了 put 方法来将字符串添加到 Trie 树中，并分配或检索字符串的唯一标识符。
class Trie:
    def __init__(self):
        # Trie 树的根节点
        self.root = TrieNode()
        # 用于给新字符串分配唯一标识符
        self.sid = 0

    def put(self, s):
        # 将字符串 `s` 添加到 Trie 树中，并返回其唯一标识符
        # 如果字符串已存在，则返回其现有标识符
        node = self.root
        for ch in s:
            index = ord(ch) - ord('a')
            if not node.children[index]:
                node.children[index] = TrieNode()
            node = node.children[index]
        if node.sid < 0:
            node.sid = self.sid
            self.sid += 1
        return node.sid


class Dijkstra:
    def __init__(self, size):
        # 图中节点的数量
        self.size = size
        # 图的邻接表表示
        self.graph = [[] for _ in range(size)]

    def add_edge(self, u, v, weight):
        # 向图中添加一条边从 `u` 到 `v`，权重为 `weight`
        self.graph[u].append((v, weight))

    def shortest_path(self, start):
        distances = [float('inf')] * self.size
        distances[start] = 0
        pq = [(0, start)]

        while pq:
            current_distance, current_vertex = heapq.heappop(pq)
            if current_distance > distances[current_vertex]:
                continue

            for neighbor, weight in self.graph[current_vertex]:
                distance = current_distance + weight
                if distance < distances[neighbor]:
                    distances[neighbor] = distance
                    heapq.heappush(pq, (distance, neighbor))

        return distances


class Solution:

    # 计算将字符串 `source` 转换为 `target` 的最小成本
    # 使用 Trie 树来存储 `original` 和 `changed` 中的字符串及其唯一标识符
    # 使用 Dijkstra 算法计算字符串之间的最短转换路径
    # 使用动态规划（通过 `dfs` 函数）来寻找最小成本的转换序列
    def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:

        inf = 1e13
        trie = Trie()
        m = len(cost)

        # 初始化 Dijkstra 算法
        dijkstra_solver = Dijkstra(m * 2)
        for i, c in enumerate(cost):
            x = trie.put(original[i])
            y = trie.put(changed[i])
            dijkstra_solver.add_edge(x, y,
                                     min(c, dijkstra_solver.graph[x][y] if y in dijkstra_solver.graph[x] else inf))

        # 计算最短路径
        shortest_paths = [dijkstra_solver.shortest_path(i) for i in range(trie.sid)]

        # 动态规划
        n = len(source)
        memo = [-1] * n

        # dfs 是一个辅助递归函数，用于动态规划。它计算从当前索引 i 开始，
        # 将 source 的剩余部分转换为 target 的最小成本。
        def dfs(i):
            # 递归函数，用于计算将 source[i:] 转换为 target[i:] 的最小成本
            if i >= n:
                return 0  # 递归边界：当 i 超过 source 的长度时，返回 0

            if memo[i] != -1:
                return memo[i]  # 如果当前索引的结果已经被计算过，则直接返回

            res = inf  # 初始化当前索引的最小成本为无穷大

            if source[i] == target[i]:
                res = dfs(i + 1)  # 如果当前字符相同，无需替换，直接计算下一个字符的成本

            p, q = trie.root, trie.root  # 初始化两个 Trie 指针，分别用于遍历 source 和 target

            # 尝试替换 source 中从索引 i 开始的所有可能的子串
            for j in range(i, n):
                index_p = ord(source[j]) - ord('a')  # 计算 source[j] 在 Trie 中的索引
                index_q = ord(target[j]) - ord('a')  # 计算 target[j] 在 Trie 中的索引

                p = p.children[index_p] if p else None  # 向下移动 source 的 Trie 指针
                q = q.children[index_q] if q else None  # 向下移动 target 的 Trie 指针

                if p is None or q is None:
                    break  # 如果任一指针到达 Trie 的末端，终止循环

                if p.sid >= 0 and q.sid >= 0:
                    # 如果当前子串在 original 和 changed 中都存在，则计算替换成本
                    # 将当前子串替换成目标子串的成本加上剩余子串转换的成本
                    res = min(res, shortest_paths[p.sid][q.sid] + dfs(j + 1))

            memo[i] = res  # 将结果存储在 memo 中，避免重复计算
            return res

        ans = dfs(0)
        return -1 if ans >= inf else int(ans)


# 示例使用
sol = Solution()
print(sol.minimumCost("abcd", "acbe", ["a", "b", "c", "c", "e", "d"], ["b", "c", "b", "e", "b", "e"],
                      [2, 5, 5, 1, 2, 20]))
